package 笔试;

public class 正则表达式匹配 {
    //动态规划
    public boolean isMatch1(String s, String p) {
        int m = s.length();
        int n = p.length();
        boolean[][] dp = new boolean[m + 1][n + 1];
        dp[0][0] = true;

        // s为空，p不为空，由于*可以匹配0个字符，所以有可能为true
        for (int i = 1; i <= n; i++) {
            if (p.charAt(i - 1) == '*' && dp[0][i - 2]) {
                dp[0][i] = true;
            }
            //            if (p.charAt(i - 1) == '*') {
            //                dp[0][i] = dp[0][i - 2];
            //            }
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if ((p.charAt(j - 1) == '.') || p.charAt(j - 1) == s.charAt(i - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else if (p.charAt(j - 1) == '*') {
                    if (p.charAt(j - 2) == s.charAt(i - 1) || p.charAt(j - 2) == '.') {
                        // 匹配0个，或多次
                        dp[i][j] = dp[i][j - 2] || dp[i - 1][j];
                    } else {
                        // 匹配0个
                        dp[i][j] = dp[i][j - 2];
                    }
                }
            }
        }
        return dp[m][n];
    }

    public boolean isMatch(String s, String p) {
        if (p.length() == 0)
            return s.length() == 0;

        //判断下一个字符是否是'*'，如果是的话，就和当前字符一起使用
        if (p.length() > 1 && p.charAt(1) == '*') {
            // p的第二个字符是 '*'
            //1,字符"*"把前面的字符消掉，也就是匹配0次
            if (isMatch(s, p.substring(2)))
                return true;
            //2,字符"*"匹配1次或多次
            return matchFirst(s, p) && isMatch(s.substring(1), p);
        } else {
            // p的第二个字符不是 '*'，判断首字符是否相同，如果相同再从第二位继续比较
            return matchFirst(s, p) && (isMatch(s.substring(1), p.substring(1)));
        }
    }

    //比较s的首字符和p的首字符是否匹配
    private boolean matchFirst(String s, String p) {
        return s.length() > 0 && p.length() > 0 && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');
    }


}
